/*
定义双向循环链表，以及基本操作
*/
#include <iostream>
using namespace std;

typedef int ElementType;
typedef struct Node Node;
struct Node {
    ElementType data;
    Node *prev;
    Node *next;
};

typedef struct LinkedList LinkedStack;
typedef struct LinkedList LinkedQueue;
typedef struct LinkedList LinkedList;
struct LinkedList {
    Node *head;
    int size;
};

// 初始化双向循环链表
LinkedList *init() {
    LinkedList *list = new LinkedList;
    list->head = new Node;
    list->head->prev = list->head;
    list->head->next = list->head;
    list->size = 0;
    return list;
}

// 在双向循环链表的第 i 个位置插入元素 x
bool insert(LinkedList *list, int i, ElementType x) {
    if (i < 1 || i > list->size + 1) {
        return false;
    }
    Node *p = list->head;
    for (int j = 0; j < i-1; ++j) {
        p = p->next;
    }
    Node *node = new Node{x, p, p->next};
    p->next->prev = node;
    p->next = node;
    ++list->size;
    return true;
}

// 删除双向循环链表的第 i 个位置的元素
ElementType remove(LinkedList *list, int i) {
    if (i < 1 || i > list->size) {
        return -1;
    }
    Node *p = list->head;
    for (int j = 0; j < i; ++j) {
        p = p->next;
    }
    ElementType x = p->data;
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    --list->size;
    return x;
}

// 获取双向循环链表的第 i 个位置的元素
ElementType get(LinkedList *list, int i) {
    if (i < 1 || i > list->size) {
        return -1;
    }
    Node *p = list->head->next;
    for (int j = 1; j < i; ++j) {
        p = p->next;
    }
    return p->data;
}

// 查找元素 x 在双向循环链表中的位置
int find(LinkedList *list, ElementType x) {
    Node *p = list->head->next;
    for (int i = 1; i <= list->size; ++i) {
        if (p->data == x) {
            return i;
        }
        p = p->next;
    }
    return -1;
}

// 输入双向循环链表
void input(LinkedList *list, int n) {
    Node *p = list->head;
    for (int i = 0; i < n; ++i) {
        Node *node = new Node;
        cin >> node->data;
        node->prev = p;
        p->next = node;
        p = node;
    }
    p->next = list->head;
    list->head->prev = p;
    list->size = n;
}

// 输出双向循环链表
void print(LinkedList *list) {
    cout << list->size << ":";
    Node *p = list->head->next;
    for (int i = 0; i < list->size; ++i) {
        cout << " " << p->data;
        p = p->next;
    }
    cout << endl;
}

void printWithEndBlank(LinkedList *list) {
    Node *p = list->head->next;
    for (int i = 0; i < list->size; ++i) {
        cout << p->data;
        if (i < list->size - 1) {
            cout << " ";
        }
        p = p->next;
    }
    cout << endl;
}

// 释放双向循环链表
void freeList(LinkedList *list) {
    Node *p = list->head->next;
    Node *q;
    for (int i = 0; i < list->size; ++i) {
        q = p->next;
        delete p;
        p = q;
    }
    delete list->head;
    delete list;
}

bool isEmpty(LinkedList *list) {
    return list->size == 0;
}

void addLast(LinkedList *list, ElementType x) {
    Node *node = new Node{x, list->head->prev, list->head};
    list->head->prev->next = node;
    list->head->prev = node;
    ++list->size;
}

ElementType removeFirst(LinkedList *list) {
    if (isEmpty(list)) {
        return -1;
    }
    Node *p = list->head->next;
    ElementType x = p->data;
    list->head->next = p->next;
    p->next->prev = list->head;
    delete p;
    --list->size;
    return x;
}

ElementType removeLast(LinkedList *list) {
    if (isEmpty(list)) {
        return -1;
    }
    Node *p = list->head->prev;
    ElementType x = p->data;
    p->prev->next = list->head;
    list->head->prev = p->prev;
    delete p;
    --list->size;
    return x;
}

// stack
void push(LinkedStack *stack, ElementType x) {
    addLast(stack, x);
}

ElementType pop(LinkedStack *stack) {
    return removeLast(stack);
}

ElementType top(LinkedStack *stack) {
    if (isEmpty(stack)) {
        return -1;
    }
    return stack->head->prev->data;
}

// queue
void enQueue(LinkedQueue *queue, ElementType x) {
    addLast(queue, x);
}

ElementType deQueue(LinkedQueue *queue) {
    return removeFirst(queue);
}

// 取队首元素
ElementType front(LinkedQueue *queue) {
    if (isEmpty(queue)) {
        return -1;
    }
    return queue->head->next->data;
}
